The Wide Finder Project

From: Tim Bray (Sep 21 2007, at 17:35)

Joe: About half as much, both CPU and elapsed. On that particular machine, perl's I/O and regexp/hash implementations were both faster.

[link]

From: Tom White (Sep 22 2007, at 09:24)

This application is indeed a perfect fit for the MapReduce paradigm - I wrote an article showing how to write a MapReduce program to analyze web logs using Hadoop here: http://developer.amazonwebservices.com/connect/entry.jspa?externalID=873&categoryID=112.

The article differs from what you are doing in that it uses Amazon EC2 to run Hadoop on rather than a single box with multiple cores. Hadoop has really been optimized for multiple machines rather than multiple cores on one machine - but it can run in that configuration. Also, the program in the article doesn't compute the most popular URLs, although this is easy to write - see the examples that come with Hadoop for inspiration.

Is it as compact and readable? It's not as compact, but that's mainly due to Java not being as expressive as Ruby. If you wrote it in Pig (http://research.yahoo.com/project/pig) it would probably be shorter than the Ruby version. Readability is harder to measure, but it's probably safe to say the MapReduce/Pig version is less familiar and therefore less easy to grasp than the Ruby version. So what would be cool is something that understands that the Ruby code is "MapReduceable", translates it into a MapReduce program and runs it transparently, exploiting all the cores available. I wonder, could a virtual machine do this one day?

[link]

From: Seth W. Klein (Sep 24 2007, at 14:19)

Jon: my test suggests not:

--- ~ S

for i in 1 2 3 4; do time ruby -e 'r=%r{GET /ongoing/When/\d\d\dx/(\d\d\d\d/\d\d/\d\d/[^ .]+) }; 1_000_000.times { r }'; done

real 0m1.539s

user 0m1.496s

sys 0m0.040s

real 0m1.544s

user 0m1.484s

sys 0m0.060s

real 0m1.544s

user 0m1.496s

sys 0m0.048s

real 0m1.545s

user 0m1.484s

sys 0m0.064s

--- ~ S

for i in 1 2 3 4; do time ruby -e '1_000_000.times { %r{GET /ongoing/When/\d\d\dx/(\d\d\d\d/\d\d/\d\d/[^ .]+) } }'; done

real 0m1.527s

user 0m1.488s

sys 0m0.036s

real 0m1.725s

user 0m1.656s

sys 0m0.068s

real 0m1.530s

user 0m1.492s

sys 0m0.032s

real 0m1.550s

user 0m1.496s

sys 0m0.052s

--- ~ S

[link]

From: Anthony Starks (Sep 25 2007, at 11:21)

Speaking of the comparison of regular expression implementations, see:

http://swtch.com/~rsc/regexp/regexp1.html

bottom line: the implementations in common scripting languages is inferior to classic implementation of programs like awk.

[link]

From: CB (Sep 26 2007, at 09:52)

I am super stupid. I just realised I had confused the meanings of user and real time. My Java concurrent version was faster when using 2 threads and batches of at least 100 lines.

I also discovered that the Java IO is around 30-40% faster if you use an InputStreamReader rather than a FileReader, and specify that your character set is US-ASCII rather than accepting the the default.

Some numbers for 1 million lines:

IO only with one thread:

real 0m2.267s

user 0m2.329s

sys 0m0.210s

Single thread:

real 0m3.208s

user 0m3.460s

sys 0m0.215s

2 Threads passing batches of 500 lines on a queue:

real 0m2.597s

user 0m4.137s

sys 0m0.294s

2 Threads using 2 pre-constructed lists for the batches of 500 and passing them through an Exchanger:

real 0m2.649s

user 0m4.171s

sys 0m0.277s

[link]

From: Tim (Sep 26 2007, at 20:05)

Bob: Yes, the space is intentional; if you read the chapter it explains why.

[link]

From: Caoyuan Deng (Sep 27 2007, at 02:20)

I wrote a solution in Erlang, with a parallel file data reading, plus a simple express matching, for a 1 million lines file (200M size), took 8.311s when -smp enable, and 10.206ms when smp disabled. The code is at:

http://blogtrader.net/page/dcaoyuan?entry=tim_bray_s_erlang_exercise

The solution spwan a lot of processes to parallel read the file to binary. Then send them to a collect_loop, collect_loop will buffered_read each chunk (when chunks order is correct), buffer_read will convert binary to small (4096 bytes here) lists, then scan_line will merge them to lines, and process_match on line.

[link]

From: RJSJr (Sep 27 2007, at 21:46)

For the map-reduce algorithm in Ruby have you looked at Starfish?

Here is the home page for the project. It looks unmaintained for the past year but may still be worth the time and effort.

A little overview page is at http://tech.rufy.com/2006/08/mapreduce-for-ruby-ridiculously-easy.html

Google "ruby starfish" for additional info.

[link]

From: Mark Hoemmen (Sep 30 2007, at 11:10)

I've written a bunch of parallel performance-oriented code for my work as well as in classes (both taking and teaching). I've found that it helps to model performance first before parallelizing. In this case, you're probably running into disk bandwidth limitations: you're on only one disk (and a laptop disk too), and not a RAID array set up to stripe across disks. Your disk can't feed your cores with data fast enough to keep them busy.

Here's a rough performance estimation. Let's say you can read data from disk into RAM at about 60 MB/s. You can stream data from RAM into your cores at around 10 GB/s. If you have 8 cores, say, then each core can read data at a rate of around 1.2 GB/s. (We assume they don't need to compute much or write much data, say for a word count.) This means that as long as there's one disk feeding all the cores, you'll never been able to feed them with data fast enough to keep up with how fast they can process it. You'll be disk-bound unless the computation per line is high enough (say for a hairy regular expression) to slow down the cores commensurately.

As mentioned in the comment stream, the right way to solve this problem is to increase bandwidth by setting up a RAID array with several disks. (Incidentally, this was much how the earlier vector supercomputers, like the Cray 1, were able to get such high memory bandwidth: they used "banked" memory, which striped the data across several memory units.) Parallelizing the computation will only help if the computation itself is very demanding.

[link]

From: Dave Thomas (Oct 04 2007, at 12:31)

Tim:

FWIW, you can speed this up by reading the initial file into memory, then processing it. Doesn't address your parallelism question, but...

Here's a version that runs on a 2,560,000 line file based on your test data. It takes 3.6s, compared to 4.6 for the original.

Dave

<pre>

counts = Hash.new(0)

RE = %r{GET /ongoing/When/\d\d\dx/(\d\d\d\d/\d\d/\d\d/[^ .]+) }

data = ARGF.read

data.scan(RE) { |ongoing| counts[ongoing] += 1 }

keys_by_count = counts.keys.sort_by { |a| -counts[a] }

keys_by_count[0 .. 9].each do |key|

puts "#{counts[key]}: #{key}"

end

</pre>

[link]

From: Will (Oct 09 2007, at 05:35)

In what way is logfile processing interesting? Sincere question.

[link]

From: nikuro (Oct 16 2007, at 05:50)

Oops! Should read:

%r{GET /ongoing/When/\d\d\dx/((?:\d\d\d\d/\d\d/\d\d/[^ .]+)) }

%r{GET /ongoing/When/\d\d\dx/((?>\d\d\d\d/\d\d/\d\d/[^ .]+)) }

[link]

From: Jordan Callicoat (Oct 16 2007, at 23:25)

A Simple Haskell version using a (very) simple, unchecked recursive descent, rather than regex:

<code><pre>

module main where

import Data.Maybe

import System (getArgs)

import Control.Monad (forM_)

import qualified Data.Map as M

import Data.List (foldl', sortBy)

import qualified Data.ByteString.Lazy.Char8 as LB

import KMP (kmpMatchLL) -- Justin Bailey, et al's KMP search for Lazy ByteStrings

countLines :: LB.ByteString -> M.Map LB.ByteString Int

countLines = foldl' count M.empty . LB.lines where

count m line =

let matches = kmpMatchLL (LB.pack "/ongoing/When/") line

uri = if (not. null) matches

then let uri1 = LB.drop ((matches !! 0) + 19) line

uri2 = LB.take (fromJust (LB.elemIndex ' ' uri1)) uri1

in case LB.elemIndex '.' uri2 of

Just idx -> LB.take idx uri2

Nothing -> uri2

else LB.empty

in if (not. LB.null) uri

then M.insertWith' (+) uri 1 m

else m

main :: IO ()

main = do

args <- getArgs

forM_ args $ \name -> (fmap countLines . LB.readFile) name >>= \m ->

let mp = ((take 10 . sortBy (flip compare `on` snd) . M.toList) m) in

mapM_ (putStrLn . (\x -> (show $ snd x) ++ ": " ++ (LB.unpack $ fst x))) mp

where on f g x y = g x `f` g y

</pre></code>

[link]

From: Aristotle Pagaltzis (Nov 09 2007, at 07:59)

Sean O’Rourke’s submission seems to be buggy; the output doesn’t line up with a doublecheck I obtained using the following command:

LC_CTYPE=C egrep -o 'GET /ongoing/When/[0-9]{3}x/[0-9]{4}/[0-9]{2}/[0-9]{2}/[^ .]+' o10k.ap | sort | uniq -c | sort -rn | head -10

[link]

From: Paul W. Homer (Nov 15 2007, at 14:32)

Maybe I've missed something (that happens :-), but your asking for an up-to-date modern way to quickly parse an old fashioned logfile?

The crude containerization of log data into a streaming log format is a legacy of a text-based paradigm of processing data, isn't it? Dumping it in a database would be better. Dumping it into something like an indexed version of db would even be faster.

The best optimizations come from doing work as early as possible and then saving it to be re-used later. If your log files entries start life as 'parsed' why 'unparse' them into a file.

Paul.

http://theprogrammersparadox.blogspot.com/

[link]